package offer;

import java.util.PriorityQueue;

/**
 * Creared with IntelliJ IDEA.
 * Description:有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 *
 * 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 * User:yxd
 * Date:2022-08-12
 * Time:10:14
 */
public class BM47 {
    public int findKth(int[] a, int n, int K) {
        // write code here
        PriorityQueue<Integer> queue = new PriorityQueue<>(K);
        for(int i = 0;i < n;i++){
            if(queue.size() < K){
                queue.add(a[i]);
            }else if(queue.peek() <= a[i]){
                queue.poll();
                queue.add(a[i]);
            }
        }
        return queue.peek();

    }
}
